



<HTML>

<HEAD>

<LINK rel="stylesheet" href="../exer.css">

</HEAD>

<BODY>

<H1>

Data Structures, Algorithms, & Applications in C++<BR>

Chapter 14, Exercise 7<BR>

<BR>

</H1>



<dl compact>

<dt> (a)

<dd>

When <em class=var>n</em> is not a power of 2, we can make the matrix dimensions

as power of 2 by adding at most <em class=var>n-1</em>rows and columns.

Therefore, the ratio <em class=var>m/n</em> is at most

<em class=var>(2n-1)/n</em> =

<em class=var>2 - 1/n</em>.

<dt> (b)

<dd>

The new rows should be added at the bottom and the new columns at

the right.  All entries in these rows and columns should be zero.

<dt> (c)

<dd>

Since <em class=var>m</em> is less than

<em class=var>2n</em>, the complexity as a function of

<em class=var>n</em> is also

Theta(<em class=var>n<sup>2.81</sup></em>).





</FONT>

</BODY>

</HTML>

